package main.Q601_700;

import java.util.*;

public class Q691_700 {
    public static void main(String[] args) {
        System.out.println("Question691：");
        System.out.println("Question692：前K个高频单词");
        System.out.println("Question693：");
        System.out.println("Question694：");
        System.out.println("Question695：岛屿的最大面积");
        System.out.println("Question696：计数二进制子串");
        System.out.println("Question697：");
        System.out.println("Question698：");
        System.out.println("Question699：");
        System.out.println("Question700：二叉搜索数中的搜索");
    }
}

class Question692 {
    public List<String> topKFrequent(String[] words, int k) {
        int length = words.length, i = 0;
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) map.put(word, map.getOrDefault(word, 0) + 1);
        String[][] counts = new String[map.size()][2];
        for (String word : map.keySet()) {
            counts[i][0] = String.valueOf(map.get(word));
            counts[i++][1] = word;
        }
        Arrays.sort(counts, new Comparator<String[]>() {
            @Override
            public int compare(String[] o1, String[] o2) {
                if (!o1[0].equals(o2[0])) {
                    return Integer.valueOf(o1[0]) - Integer.valueOf(o2[0]);
                } else {
                    char[] str1 = o1[1].toCharArray(), str2 = o2[1].toCharArray();
                    int j = 0;
                    while (j < str1.length && j < str2.length) {
                        if (str1[j] != str2[j]) return str2[j] - str1[j];
                        j++;
                    }
                    if (j < str1.length) return -1;
                    else return 1;
                }
            }
        });
        List<String> list = new ArrayList<>();
        for (int j = 0; j < k; j++) list.add(counts[counts.length - 1 - j][1]);
        return list;
    }
}

class Question695 {
    public int process(int[][] grid, int row, int col) {
        int count = 1, r = grid.length, c = grid[0].length;
        grid[row][col] = 0;//该区域被标记
        if (row - 1 >= 0 && grid[row - 1][col] == 1) count += process(grid, row - 1, col);//上
        if (row + 1 < r && grid[row + 1][col] == 1) count += process(grid, row + 1, col);//下
        if (col - 1 >= 0 && grid[row][col - 1] == 1) count += process(grid, row, col - 1);//左
        if (col + 1 < c && grid[row][col + 1] == 1) count += process(grid, row, col + 1);//右
        return count;
    }

    public int maxAreaOfIsland(int[][] grid) {
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int area = 0;
                if (grid[i][j] == 1)//该位置为未被标记的岛屿
                    area = process(grid, i, j);//该岛屿的面积
                maxArea = Math.max(area, maxArea);
            }
        }
        return maxArea;
    }
}

class Question696 {
    public int countBinarySubstrings(String s) {
        List<Integer> counts = new ArrayList<>();
        int ptr = 0, n = s.length();
        while (ptr < n) {
            char c = s.charAt(ptr);
            int count = 0;
            while (ptr < n && s.charAt(ptr) == c) {
                ++ptr;
                ++count;
            }
            counts.add(count);
        }
        int result = 0;
        for (int i = 1; i < counts.size(); ++i) {
            result += Math.min(counts.get(i), counts.get(i - 1));
        }
        return result;
    }
}

class Question697 {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            } else map.put(nums[i], new int[]{1, i, i});
        }
        int maxNum = 0, minLen = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] arr = entry.getValue();
            if (maxNum < arr[0]) {
                maxNum = arr[0];
                minLen = arr[2] - arr[1] + 1;
            } else if (maxNum == arr[0]) {
                if (minLen > arr[2] - arr[1] + 1) minLen = arr[2] - arr[1] + 1;
            }
        }
        return minLen;
    }
}

class Question700 {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode result = null;
        while (root != null && root.val != val) {
            if (root.val < val) root = root.right;
            else if (root.val > val) root = root.left;
        }
        result = root;
        return result;
    }
}